%% file_comment

-module(bellmann_ford).

%% ====================================================================
%% API functions
%% ====================================================================
-export([
         bellmann_ford/2,
         test_negative_cycle/2
        ]).

%% ====================================================================
%% External exports
%% ====================================================================

%% Graphentheorethische Kontepte und Algorithmen. Seite 183
bellmann_ford(Graph, Start_Vertex_ID) ->
    Vertexes = graph:getVertexes(Graph),
    N = length(Vertexes) - 1,
    T = tableau:init(Vertexes, Start_Vertex_ID),
    for(Graph, T, N, 1).

%% ====================================================================
%% Internal functions
%% ====================================================================

%% Graphentheorethische Kontepte und Algorithmen. Seite 183
%% for k := 1,...,n - 1 do
for(Graph, T, N, K) ->
    if
        K < N -> EdgeList = graph:getEdges(Graph),
                 T_New = forall(Graph, T, EdgeList),
                 for(Graph, T_New, N, (K + 1));
        true  -> T
    end.

%% Graphentheorethische Kontepte und Algorithmen. Seite 183
%% for all (u, v) el R do
forall(_Graph, T, []) ->
    T;
forall(Graph, T, EdgeList) ->
    [Edge| Tail] = EdgeList,
    T_New = test(T, graph:getSource(Graph, Edge), graph:getTarget(Graph, Edge), graph:getValE(Graph, Edge, weight)),
    forall(Graph, T_New, Tail).

%% Graphentheorethische Kontepte und Algorithmen. Seite 173
test(T, U, V, C) ->
    case tableau:getD(T, V) > (tableau:getD(T, U) + C) of
        true  -> T1 = tableau:setD(T, V, (tableau:getD(T,U) + C)),
                 tableau:setPi(T1, V, U);
        false -> T
    end.
          
%% Graphentheorethische Kontepte und Algorithmen. Seite 184
test_negative_cycle(Graph, Tableau) ->
    test_neg_cycle(Graph, graph:getEdges(Graph), Tableau).
    
test_neg_cycle(_, [], _) ->
    'nein';
test_neg_cycle(Graph, Edgelist, Tableau) ->
    [Edge | T] = Edgelist,
    V = graph:getTarget(Graph, Edge),
    U = graph:getSource(Graph, Edge),
    case tableau:getD(Tableau,V) > (tableau:getD(Tableau,U) + graph:getValE(Graph, Edge, 'weight')) of
        true -> 'ja';
        false -> test_neg_cycle(Graph, T, Tableau)
    end.

                                      

